package stack_queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 1047. 删除字符串中的所有相邻重复项
 *
 * @author Api
 * @date 2023/10/15 23:41
 */
public class Code1047_DeleteAllAdjacentDuplicatesInTheString {
    //==================================================================================================================
    //使用Deque作为堆栈
    public String removeDuplicates(String s) {
        Deque<Character> deque = new ArrayDeque<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            if (deque.isEmpty() || deque.peek() != ch) {
                deque.push(ch);
            } else {
                deque.pop();
            }
        }
        String str = "";
        // 剩余的元素即为不重复的元素
        while (!deque.isEmpty()) {
            str = deque.pop() + str;
        }
        return str;
    }

    //==================================================================================================================
    // 拿字符串直接作为栈，省去了栈还要转为字符串的操作。
    public String removeDuplicates1(String s) {
        // 将res作为栈
        // 也就可以用StringBuilder来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuilder res = new StringBuilder();
        // top为res的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当top > 0,即栈中有字符串时，当前字符如果和栈中的字符相等，弹出栈顶字符，同时top--；
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
            } else {// 否则该字符入栈，同时top++
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }

    //==================================================================================================================\
    // 双指针
    public String removeDuplicates2(String s) {
        char[] ch = s.toCharArray();
        int fast = 0;
        int slow = 0;
        while (fast < s.length()) {
            // 直接用fast指针覆盖slow指针的值
            ch[slow] = ch[fast];
            // 遇到前后相同值时，就跳过，即slow指针后退一步，下次循环就可以直接被覆盖掉了
            if (slow > 0 && ch[slow] == ch[slow - 1]) {
                slow--;
            } else {
                slow++;
            }
            fast++;
        }
        return new String(ch, 0, slow);
    }
}
